/// [Coin sums](https://projecteuler.net/problem=31)
fn main() {
    println!(
        "The different ways can £2 be made using any number of coins is {}",
        coin_sums(200, 200)
    );
}

fn coin_sums(sum: usize, max: usize) -> usize {
    if sum < 2 || max < 2 {
        return 1;
    }
    let mut new = coin_next(max);
    while new > sum {
        new = coin_next(new);
    }
    (0..=(sum / max))
        .map(|i| coin_sums(sum - max * i, new))
        .fold(0, |s, x| s + x)
}

fn coin_next(coin: usize) -> usize {
    if coin > 200 {
        (coin / 200) * 100
    } else if coin > 20 {
        (coin / 20) * 10
    } else {
        coin / 2
    }
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test1() {
        assert_eq!(coin_sums(1, 2), 1);
        assert_eq!(coin_sums(1, 5), 1);
    }
    #[test]
    fn test2() {
        assert_eq!(coin_sums(2, 2), 1);
        assert_eq!(coin_sums(2, 5), 2);
    }
    #[test]
    fn test3() {
        assert_eq!(coin_sums(3, 2), 1);
        assert_eq!(coin_sums(3, 5), 2);
    }
    #[test]
    fn test4() {
        assert_eq!(coin_sums(4, 2), 1);
        assert_eq!(coin_sums(4, 5), 3);
    }
    #[test]
    fn test5() {
        assert_eq!(coin_sums(5, 2), 1);
        assert_eq!(coin_sums(5, 5), 3);
        assert_eq!(coin_sums(5, 10), 4);
    }
}
